Batch 3 - Class 166 - Knight Placements

• Answer: 26 minutes 40 seconds past noon

• Can you start from a square on a 3x3 chessboard with a knight, and create a tour, i.e. cover all squares?
• Answer: No. There is no entry and no exit from central square. If you were to exclude the central square, you can actually cover all other squares and bring the knight back to the starting point
• Can you take a Knight on a tour and bring it back to the initial square in a 5x5 chessboard?
• Answer: No. Such a Knight tour would have to have equal number of black and white squares, whereas a 5x5 board has unequal number of black and white squares
• Does a Knight's path exist, i.e. you are not required to return to the original position?
• Answer: Yes. Example below:

• Can you construct a Knight's tour on a 4x4 board (you are not required to come back to the original square)
• Answer: No. Note that opposite corner squares connects only to the same two central squares. Hence one must start from a corner square and end at an adjacent corner square (the other two corners being visited in course of the tour.) Work with this starting point to systematically show that a whole tour is not possible. We can also visualize this in form of a graph (vertices being squares, and edges being valid knight moves)
• Note that Knight graphs are bipartite, i.e. you can put vertices in two buckets and edges only go across - it is easy to see this by coloring alternate positions of the knight black and white.
• The paths such as above are Hamiltonian paths (they visit each vertex exactly once). In general, finding Hamiltonian paths is a "hard" problem. However, Knights tours can be found "easily" (linear), and exist for all chessboards 5x5 and larger.

• Can you place pieces on a 8x8 chess board so that each row has different number of pieces, but each column has the same number of pieces?
• Lets start with a smaller board. Try 2x2, 3x3, 4x4 and so on
• Do you see a pattern? If so, can you extrapolate to 8x8
• For 8x8, each row can only have 0 to 8 pieces. What is the total? If each column has to have equal number of pieces, what should that number be (Hint: multiple of 8)? If each column has 4, then the rows must have 0,1,2,3 and 5,6,7,8 - can you think pairwise build up where for each pair, columns retain equal numbers?
• Is there a difference between odd-sized boards and even-sized boards?
• For odd boards, you can either exclude 0 or n; rest is the same

• Can you construct a knight's tour on a 8x8 board. Note that the problem is solvable, and somewhat hard. Try to solve the problem. For an interesting discussion, see https://en.wikipedia.org/wiki/Knight%27s_tour